Tu Misión 🎯
Reconecta $N$ planetas, dados como coordenadas 2D, mediante una red de "Hiperrutas" de costo mínimo.
- Objetivo: Conecta todos los $N$ planetas (vértices) para que todos sean alcanzables (directamente o indirectamente).
- Objetivo: Encuentra el diseño de red que minimice el **costo total**.
Análisis 🛰️
El costo de una hiperruta (arista) es la distancia euclidiana:
$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$
- Una hiperruta puede construirse entre cualquierdos planetas.
- Esto significa que tenemos un grafo completo (denso).
La Solución ⚙️
Este es un problema clásico de Árbol de Expansión Mínima (MST) problema.
- Algoritmo: La pista recomienda el algoritmo de Prim (la versión $O(V^2)$), que es ideal para grafos densos.
- Punto de partida: Iniciaremos nuestro algoritmo desde el Planeta 0 para obtener un resultado consistente.
Un grafo completo (izquierda) tiene todas las aristas posibles. El MST (derecha) es el subconjunto más económico de aristas que conecta todos los vértices.